#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2018/9/3 19:55
# @Author  : yangdy
# @Email   : yangdy@egu360.com
# @File    : lca.py
# @Software: PyCharm

# Definition for a binary tree node.


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

    def __str__(self):
        return self.val


class Solution:
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        class LCA:
            def __init__(self):
                self.m = {}

            def reset(self):
                self.m = {}

            def find(self, x):
                if self.m.get(x):
                    if self.m[x] == x:
                        return x
                    self.m[x] = self.find(self.m[x])
                    return self.m[x]
                else:
                    self.m[x] = x
                    return x

            def merge(self, x, y):
                self.m[self.find(y)] = x

        lca = LCA()

        question = {p.val: [q.val],
                    q.val: [p.val]}
        ans = {p.val: {},
               q.val: {}}
        vis = {}

        def work(nd=root):
            for p in [nd.left, nd.right]:
                if p:
                    work(p)
                    lca.merge(nd.val, p.val)
                    if not vis.get(p.val):
                        vis[p.val] = True
            if question.get(nd.val):
                for x in question[nd.val]:
                    if vis.get(x):
                        ans[nd.val][x] = lca.find(x)
        work()
        print(question)
        print(ans)


def main():
    solve = Solution()
    ll = [3, 5, 1, 6, 2, 0, 8, None, None, 7, 4]
    tree = [TreeNode(ll[0])]
    q = []
    for i in range(1, len(ll)):
        print('i =', i)
        if ll[i] is not None:
            print('ll:')
            p = i // 2
            print('p =', p)
            node = TreeNode(ll[i])
            print(tree)
            if tree[p]:
                if i % 2 == 0:
                    tree[p].left = node
                else:
                    tree[p].right = node
            tree.append(node)
            if i == 3:
                q.append(node)
            elif i == 9:
                q.append(node)
        else:
            tree.append(None)
    root = tree[0]
    print(q)

    solve.lowestCommonAncestor(root, q[0], q[1])


if __name__ == '__main__':
    main()





